Algorytm Earliest-Deadline-First (EDF)

Algorytm Earliest-Deadline-First (ang. Earliest Deadline First), w skrócie EDF, jest jedną z najważniejszych metod planowania zadań w systemach czasu rzeczywistego. Jego podstawową zasadą jest przydzielanie najwyższego priorytetu procesowi (lub zadaniu), którego termin końcowy (deadline) jest najbliższy bieżącemu momentowi czasu. EDF jest algorytmem przerywalnym (preemptive) i dynamicznie przydzielanym priorytetom.

Historia

Pierwsze formalne opracowanie algorytmu EDF pojawiło się w literaturze w latach 1970-1980 w kontekście kolejkowania w systemach operacyjnych. W 1974 roku C. L. Liu i James W. Layland opublikowali klasyczny artykuł „Scheduling Algorithms for Multiprocessor Real-Time Systems”, w którym zaprezentowali EDF jako optymalny algorytm dla jednowątkowych, preemptowalnych systemów zadań okresowych.

Podstawowe założenia

System jest jednowątkowy lub wielowątkowy (w wersji multiprocesorowej algorytm nazywany jest global EDF).
Zadania są okresowe lub jednorazowe, a każdy z nich posiada określony deadline (czas, do którego zadanie musi zostać zakończone).
Priorytet zadania jest określany dynamicznie: im wcześniejszy deadline, tym wyższy priorytet.
Algorytm jest przerywalny – w razie pojawienia się nowego zadania o wcześniejszym deadline bieżące zadanie może zostać przerwane.

Działanie algorytmu

W momencie wystąpienia zdarzenia (np. przybycie nowego zadania) system wylicza deadline dla każdego gotowego zadania.
Wszystkie gotowe zadania są sortowane rosnąco według wartości deadline.
Procesor przydzielany jest zadaniu o najniższym deadline. Jeśli w trakcie wykonywania pojawi się zadanie o jeszcze wcześniejszym deadline, bieżące zadanie zostaje przerwane i w kolejce priorytetowej przeskakuje na drugie miejsce.

Formalna charakterystyka

Algorytm EDF jest optymalny w sensie, że jeśli istnieje jakikolwiek planista zdolny do spełnienia wszystkich deadline'ów w systemie jednowątkowym, to EDF również je spełni. Optymalność ta wynika z następujących własności:

Żywotność (feasibility) – jeżeli suma wykorzystań procesora (ang. utilization) U spełnia warunek U ≤ 1, to EDF zawsze znajdzie wykonalny harmonogram.
Brak potrzeby znajomości okresu zadań przy planowaniu w trybie dynamicznym – priorytet zależy wyłącznie od aktualnych wartości deadline.

Złożoność obliczeniowa

Implementacja EDF wymaga utrzymywania kolejki priorytetowej (np. kopca) posortowanej według deadline. Dlatego podstawowa operacja wyboru kolejnego zadania ma złożoność O(log n), gdzie n jest liczbą gotowych zadań. W praktyce, przy niewielkiej liczbie zadań, można używać listy posortowanej, uzyskując O(n) w najgorszym wypadku.

Warianty i rozszerzenia

Global EDF (G-EDF) – planowanie w środowiskach wieloprocesorowych, w którym wszystkie zadania konkurują o wspólne zasoby procesora.
Partitioned EDF – zadania są najpierw przydzielane do poszczególnych procesorów (partycjonowanie), a następnie na każdym procesorze stosowany jest klasyczny EDF.
EDF with Dithering – modyfikacja wprowadzająca losowy opóźnienie w przydzielaniu priorytetów w celu redukcji zjawiska głodzenia zadań.

Porównanie z innymi algorytmami planowania

Algorytm	Typ priorytetu	Optymalność (jednowątkowy)	Kompleksowość
Earliest-Deadline-First (EDF)	Dynamiczny	Tak, przy U ≤ 1	O(log n)
Rate-Monotonic (RM)	Statyczny	Nie, jedynie U ≤ n(2^{1/n} - 1)	O(1)
Least-Laxity-First (LLF)	Dynamiczny	Optymalny, ale wymaga stałego przeliczania laxity	O(log n)

Zastosowania

EDF znajduje zastosowanie w wielu dziedzinach, w których kluczowe jest spełnienie ścisłych terminów:

Systemy wbudowane – kontrola procesów przemysłowych, systemy lotnicze.
Aplikacje multimedialne – odtwarzanie strumieni wideo i audio w czasie rzeczywistym.
Telekomunikacja – zarządzanie pakietami w sieciach o wysokiej przepustowości.
Robotyka – koordynacja ruchów i czujników w systemach autonomicznych.

Ograniczenia i wyzwania

Mimo swojej prostoty i optymalności, EDF posiada pewne ograniczenia:

W środowiskach z dużą liczbą zadań wymaga precyzyjnego śledzenia deadline'ów, co może generować narzut przy dużym n.
W systemach miękkiego czasu rzeczywistego jedynie niewielkie przekroczenia deadline'ów są akceptowalne – EDF nie zapewnia kontrolowanej degradacji jakości usług.
W wersji multiprocesorowej (G-EDF) problem zawieszania (priority inversion) oraz konieczność synchronizacji wątków może komplikować implementację.

Implementacje i biblioteki

Wiele systemów operacyjnych czasu rzeczywistego (RTLinux, FreeRTOS, VxWorks) oferuje wbudowane wsparcie dla planowania EDF lub umożliwia jego implementację jako moduł rozszerzeń.

Przykładowy kod (pseudo)

while (true) {
    // Pobierz wszystkie gotowe zadania
    readyQueue = getReadyTasks();
    // Posortuj według najbliższego deadline
    sortByDeadline(readyQueue);
    // Wybierz zadanie o najwcześniejszym deadline
    currentTask = readyQueue[0];
    execute(currentTask);
}